package leetcode.search;

import java.util.ArrayList;
import java.util.List;

/**
 编写一个程序，通过填充空格来解决数独问题。

 数独的解法需 遵循如下规则：

 数字 1-9在每一行只能出现一次。
 数字1-9在每一列只能出现一次。
 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
 数独部分空格内已填入了数字，空白格用'.'表示。
 */
public class SolveSudoku37 {

    public static void main(String[] args) {
    }

    public void solveSudoku(char[][] board) {
        boolean [][]colV = new boolean[9][10];//列
        boolean [][]rowV = new boolean[9][10];//行
        boolean [][][]grid = new boolean[3][3][10];

        for (int i = 0; i < board.length; i++) {//每一行
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]=='.')
                    continue;

                int num = board[i][j] - '0';
                rowV[i][num] = true;
                colV[j][num] =true;
                grid[i/3][j/3][num] = true;
            }
        }

        boolean find = find(board,0, 0, colV, rowV, grid);
    }

    private boolean find(char[][] board,//解
                      int row, int col,//访问参数 row：当前所在行数
                      boolean [][]colV, boolean [][]rowV,boolean[][][]grid){//访问状态

        if(col==9){//这就是一个解了
            col = 0;
            row++;
            if(row == 9){//搞定了，最后一个数了
                return true;
            }
        }

        if(board[row][col]=='.'){

            for (int j = 1; j < 10; j++) {
                if(colV[col][j] ||rowV[row][j] || grid[row/3][col/3][j])
                    continue;

                board[row][col] = (char)('0' + j);; //修改状态
                colV[col][j] = true;
                rowV[row][j] = true;
                grid[row/3][col/3][j] = true;

                if(find(board,row,col+1,colV,rowV,grid)) {//在这列，看看下一行能不能继续
                    return true;
                }

                board[row][col] = '.';//回改状态
                colV[col][j] = false;
                rowV[row][j] = false;
                grid[row/3][col/3][j] =false;
            }
        }else {
            return find(board,row,col+1,colV,rowV,grid);
        }
        return false;
    }

}